A Simple Attack on Some Clock-Controlled Generators

摘要

We present a new approach to edit distance attacks on certainclock-controlled generators, which applies basic concepts of Graph Theory tosimplify the search trees of the original attacks in such a way that only themost promising branches are analyzed. In particular, the proposed improvementis based on cut sets defined on some graphs so that certain shortest pathsprovide the edit distances. The strongest aspects of the proposal are that theobtained results from the attack are absolutely deterministic, and that manyinconsistent initial states of the target registers are recognized beforehandand avoided during search.